#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <bitset>
using namespace std;

const int NUM = 50000000;
const int INT_BIT = 32;
const int SHIFT = 5;
const int MASK = 0x1f;
const char* FILE_NAME = "data.in";

bitset<NUM> mySet;
int arr[1 + NUM/32];

void set (int n)
{
	arr[n>>SHIFT] |=  ( 1<<(n&MASK) );
}

bool exist (int n)
{
	return arr[n>>SHIFT] & ( 1<<(n&MASK) );
}

void prepareData()
{
	FILE* pFile = fopen(FILE_NAME, "w");
	int i, tmp;
	srand( time(NULL) );
	for (i = 0; i < NUM; i ++)
	{
//		tmp = rand() % NUM;
		tmp = i;
		fprintf(pFile, "%d\n", tmp);
	}
	fclose(pFile);
}

void testMyBitSet ()
{
	int i, tmp;
	FILE* pFile;
	pFile = fopen(FILE_NAME, "r");
	while ( fscanf(pFile, "%d", &tmp) != EOF )
	{
		set(tmp);
	}
	for (i = 0; i < NUM; i ++)
	{
		if ( exist(i) )
		{
//			printf("%d\n", i);
		}
	}
	fclose(pFile);
}

void testSTLBitSet ()
{
	int i, tmp;
	FILE* pFile;
	pFile = fopen(FILE_NAME, "r");
	while ( fscanf(pFile, "%d", &tmp) != EOF )
	{
		mySet.set(tmp, 1);	
	}
	for (i = 0; i < NUM; i ++)
	{
		if ( mySet.test(i) )
		{
//			printf("%d\n", i);
		}
	}
}

int main ()
{
	time_t s1, e1, s2, e2;
	prepareData();
	
	s1 = time(NULL);
	testMyBitSet();
	e1 = time(NULL);

	s2 = time(NULL);
	testSTLBitSet();
	e2 = time(NULL);

	printf("my bit set: %d ms\n", e1 - s1);
	printf("stl bit set: %d ms\n", e2 - s2);

	return 0;
}